n=4
def can_set(one_board,i,j):
    x,y=i-1,j-1
    while x>=0 and y>=0:
        if one_board[x][y]==".":
            #保证这一行和这一列同时没有元素
            x-=1
            y-=1
            continue
        if one_board[x][y]=="Q":
            return False
    x,y=i-1,j+1
    while x>=0 and y>=0 and y<n:
        if one_board[x][y]==".":
            x-=1
            y+=1
            continue
        if one_board[x][y]=="Q":
            return False
    return True
def dfs(n,depth,one_board,row_state,col_state,res):
    if depth==n:
        print("得到的一种可能的结果：")
        print(one_board)
        res.append(one_board)
        return None
    for i in range(n):
        for j in range(n):
            #双重循环遍历图
            if one_board[i][j]=="." and row_state[i]==False and col_state[j]==False:
                #该位置没有被占掉,且相同的行和相同的列上都不存在棋子
                #接下来是需要判断相同的斜边上是否存在棋子
                if can_set(one_board,i,j):
                    #表示当前位置的斜方向上也不存在
                    one_board[i][j]="Q"
                    row_state[i],col_state[j]=True,True
                    dfs(n,depth+1,one_board,row_state,col_state,res)
                    one_board[i][j]="."
                    row_state[i]=False
                    col_state[j]=False
def solveNQueens(n):
    #行的状态列表
    #列的状态列表
    row_state=[False for _ in range(n)]
    col_state=[False for _ in range(n)]
    # print("row_state:",row_state)
    # print("col_state:",col_state)
    #存放结果的矩阵
    res=[]
    #存放一次中路径的矩阵
    one_board=[["." for _ in range(n)] for _ in range(n)]
    #深度优先遍历
    dfs(n,0,one_board,row_state,col_state,res)
    # print(res)
solveNQueens(n)

